package summary;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 海琳琦
 * @Date: 2022/8/7 17:41
 */
public class Title140 {

    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        StringBuilder temp = new StringBuilder();
        int n = s.length();
        int[] flag = new int[n];
        dfs(s, wordDict, flag,  temp, result,n,0);
        return result;
    }

    private void dfs(String s, List<String> wordDict, int[] flag, StringBuilder temp, List<String> result, int n, int cur) {
        if (cur >= n) {
            result.add(temp.toString().substring(0, temp.length() - 1));
            return;
        }
        if (flag[cur] == 1) {
            //访问过
            return;
        }
        for (int i = cur; i < n; i++) {
            String str = s.substring(cur, i + 1);
            if (wordDict.contains(str)) {
                temp.append(str+" ");
                dfs(s, wordDict, flag, temp, result, n, i + 1);
                temp.delete(temp.length() - str.length() - 1, temp.length());
            }
        }
        flag[cur] = 0;
    }


    public static void main(String[] args) {

    }
}
